/**
 * Tree.java created by zhangzhidong 
 * at 下午7:59:34 2015年8月3日
 */
package tree;

/**
 * @author Alex
 *
 */
public class Tree {
	private Node root;
	public Node find(int key){
		Node current = root;
		while(key!=current.iData){
			if(key<current.iData){
				current = current.leftChild;
			}else{
				 
				current = current.rightChild;
			}
			if(current == null){
				return null;
				}
		}
		return current;	
	}
	public void insert(int id,double dd){
		Node newNode = new Node();
		newNode.iData = id;
		newNode.dData = dd;
		if(root ==null){
			root = newNode;
		}else{		
			Node current = root;
			Node parent=null;
			while(true){
				parent =current;
				if(newNode.dData<current.dData){
					current = current.leftChild;
					if(current==null){
						parent.leftChild = newNode;
					}
					return ;
					
					
				}else{
					current = current.rightChild;
					if(current==null){
						parent.rightChild =  newNode;
						return ;
					}
				}		
			}
		}
	}
	private void inOrder(Node localRoot){
		if(localRoot!=null){
			inOrder(localRoot.leftChild);
			//visit it
			System.out.println(localRoot.dData);
			inOrder(localRoot.rightChild);
		}
	}
	public Node minium(){
		Node result =root, current =  root;
		while(root!=null){
			result = current;
			current=root.leftChild;			
		}
		return result;		
	}	
	public Node maxium(){
		Node result =root, current =  root;
		while(root!=null){
			result = current;
			current=root.rightChild;			
		}
		return result;		
	}
	
	
	
	//删除叶子节点的情况
	public boolean delete(int key){
		Node current =root,parent = root;
		boolean isLeftChild = true;
		if(current == null) return false;
	while(key!=current.iData){
		parent = current;
		if(key<current.dData){
			isLeftChild = true;
			current = current.leftChild;
		}else{
			isLeftChild  = false;
			current = current.rightChild;
		}
		if(current==null) return false;//这种是没找到
	}
	//找到的是叶子节点
	if(current.leftChild==null && current.rightChild==null ){
		if(current == root) {root =null;}
		else if(isLeftChild){
			parent.leftChild =null;
		}else{
			parent.rightChild = null;
		}
		return true;
	}else if(current.rightChild==null){//找到的节点只有一个节点
		//该节点有一个左节点
		if(isLeftChild){
			parent.leftChild=current.leftChild;
		}else{
			parent.rightChild = current.leftChild;
		}
		return true;
	}else if(current.leftChild == null){
		//有一个右节点
		if(isLeftChild){
			parent.leftChild=current.rightChild;
		}else{
			parent.rightChild =current.rightChild;
		}
		return true;	
	}else {
		//该节点有两个子节点
		Node successor  =getSuccessor(current);
		//如果后继节点是被删除节点的直接右子节点,它肯定不会有左节点
		if(current == root){
			root =successor;
		}else if(isLeftChild){
			parent.leftChild=successor;
		}else{
			parent.rightChild = successor;
		}
		successor.leftChild=current.leftChild;
		return true;
	}	
}
	//返回被删除节点的后继节点
	private  Node getSuccessor(Node delNode){
		Node successorParent = delNode;
		Node successor  = delNode;
		Node current = successor.rightChild;
		while(current!=null){
			successorParent = successor;
			successor =  current;		
			current = current.leftChild;		
		}
		if(successor != delNode.rightChild){
			//排除被删除节点的右节点的左节点为空的情况
			//如果被删除节点的右节点有左节点就干这些事,也就是说后继不是被删除节点的直接右节点
			successorParent.leftChild = successor.rightChild;
			successor.rightChild=delNode.rightChild;	//后继替换被删除节点
		}
		return successor;
	}	
}
